package leet135candy135

// https://leetcode-cn.com/problems/candy/
// 思路：
// 1. 先给每个孩子一个糖果
// 2. 从左到右遍历，如果当前孩子的评分比前一个孩子高，则给当前孩子比前一个孩子多一个糖果
// 3. 从右到左遍历，如果当前孩子的评分比后一个孩子高，则给当前孩子比后一个孩子多一个糖果
// 4. 最后计算总糖果数
// 5. 返回总糖果数
// 复杂度分析：
// 时间复杂度：O(n)，其中 n 是孩子的数量。我们只需要遍历两次数组。
// 空间复杂度：O(n)，我们需要一个数组来存储每个孩子的糖果数。
func Candy(ratings []int) int {
	n := len(ratings)
	if n == 0 {
		return 0
	}
	candies := make([]int, n)
	// Step 1: Initialize each child with one candy
	for i := range candies {
		candies[i] = 1
	}

	// Step 2: Left to right pass
	for i := 1; i < n; i++ {
		if ratings[i] > ratings[i-1] {
			candies[i] = candies[i-1] + 1
		}
	}

	// Step 3: Right to left pass
	for i := n - 2; i >= 0; i-- {
		if ratings[i] > ratings[i+1] {
			candies[i] = max(candies[i], candies[i+1]+1)
		}
	}

	// Step 4: Calculate total candies
	totalCandies := 0
	for _, candy := range candies {
		totalCandies += candy
	}

	return totalCandies
}

// max returns the maximum of two integers
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
